#include <bits/stdc++.h>
using namespace std;

/*
3542. 将所有元素变为 0 的最少操作次数
已解答
中等
相关标签
premium lock icon
相关企业
提示
给你一个大小为 n 的 非负 整数数组 nums 。你的任务是对该数组执行若干次（可能为 0 次）操作，使得 所有 元素都变为 0。

在一次操作中，你可以选择一个子数组 [i, j]（其中 0 <= i <= j < n），将该子数组中所有 最小的非负整数 的设为 0。

返回使整个数组变为 0 所需的最少操作次数。

一个 子数组 是数组中的一段连续元素。
 

示例 1：

输入: nums = [0,2]

输出: 1

解释:

选择子数组 [1,1]（即 [2]），其中最小的非负整数是 2。将所有 2 设为 0，结果为 [0,0]。
因此，所需的最少操作次数为 1。
示例 2：

输入: nums = [3,1,2,1]

输出: 3

解释:

选择子数组 [1,3]（即 [1,2,1]），最小非负整数是 1。将所有 1 设为 0，结果为 [3,0,2,0]。
选择子数组 [2,2]（即 [2]），将 2 设为 0，结果为 [3,0,0,0]。
选择子数组 [0,0]（即 [3]），将 3 设为 0，结果为 [0,0,0,0]。
因此，最少操作次数为 3。
示例 3：

输入: nums = [1,2,1,2,1,2]

输出: 4

解释:

选择子数组 [0,5]（即 [1,2,1,2,1,2]），最小非负整数是 1。将所有 1 设为 0，结果为 [0,2,0,2,0,2]。
选择子数组 [1,1]（即 [2]），将 2 设为 0，结果为 [0,0,0,2,0,2]。
选择子数组 [3,3]（即 [2]），将 2 设为 0，结果为 [0,0,0,0,0,2]。
选择子数组 [5,5]（即 [2]），将 2 设为 0，结果为 [0,0,0,0,0,0]。
因此，最少操作次数为 4。
 

提示:

1 <= n == nums.length <= 105
0 <= nums[i] <= 105
*/

// 法一
class Solution {
public:
    int minOperations(vector<int>& nums) {
        // 单调栈
        int ans = 0;
        stack<int> st;
        for (int v : nums) {
            // 单增  pop >= cur item
            while (!st.empty() && st.top() > v) {
                st.pop();
                ans++;
            }
            // continue 0
            if (v == 0) continue;
            // push item >= top
            if (st.empty() || st.top() < v) st.push(v);
        }
        return ans + st.size();
    }
};

// 法二
class Solution {
public:
    int minOperations(vector<int>& nums) {
        // 单调栈
        int ans = 0;          // 记录操作次数
        int top = -1;         // 模拟栈顶指针（-1表示空栈），栈维护递增不重复序列
        for (int x : nums) {
            // 弹出栈中比当前x大的元素（需先处理更大元素，每弹出1次记1次操作）
            while (top >= 0 && x < nums[top]) {
                top--;
                ans++;
            }
            // 栈空或x与栈顶不同，压入x（去重，保持递增）
            if (top < 0 || x != nums[top]) nums[++top] = x;
        }
        // ans：弹出操作数；top+1：栈中元素数（对应段数）；nums[0]>0：排除全0场景的多余计数
        return ans + top + (nums[0] > 0);
    }
};

// stack 有开销 直接模拟栈 性能更高
